/*
 * Copyright 2008 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package java.util;

import com.google.gwt.core.client.JavaScriptObject;

/**
 * Implementation of Map interface based on a hash table. <a
 * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html">[Sun
 * docs]</a>
 *
 * @param <K> key type
 * @param <V> value type
 */
abstract class AbstractHashMap<K, V> extends AbstractMap<K, V> {
    /*
    * Implementation notes:
    *
    * String keys are stored in a separate map from non-String keys. String keys
    * are mapped to their values via a JS associative map, stringMap. String keys
    * could collide with intrinsic properties (like watch, constructor) so we
    * prepend each key with a ':' inside of stringMap.
    *
    * Integer keys are used to index all non-string keys. A key's hashCode is the
    * index in hashCodeMap which should contain that key. Since several keys may
    * have the same hash, each value in hashCodeMap is actually an array
    * containing all entries whose keys share the same hash.
    */
    private final class EntrySet extends AbstractSet<Entry<K, V>> {

        @Override
        public void clear() {
            AbstractHashMap.this.clear();
        }

        @Override
        public boolean contains(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
                Object key = entry.getKey();
                if (AbstractHashMap.this.containsKey(key)) {
                    Object value = AbstractHashMap.this.get(key);
                    return AbstractHashMap.this.equals(entry.getValue(), value);
                }
            }
            return false;
        }

        @Override
        public Iterator<Entry<K, V>> iterator() {
            return new EntrySetIterator();
        }

        @Override
        public boolean remove(Object entry) {
            if (contains(entry)) {
                Object key = ((Map.Entry<?, ?>) entry).getKey();
                AbstractHashMap.this.remove(key);
                return true;
            }
            return false;
        }

        @Override
        public int size() {
            return AbstractHashMap.this.size();
        }
    }

    /**
     * Iterator for <code>EntrySetImpl</code>.
     */
    private final class EntrySetIterator implements Iterator<Entry<K, V>> {
        private final Iterator<Map.Entry<K, V>> iter;
        private Map.Entry<K, V> last = null;

        /**
         * Constructor for <code>EntrySetIterator</code>.
         */
        public EntrySetIterator() {
            List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();
            if (nullSlotLive) {
                list.add(new MapEntryNull());
            }
            addAllStringEntries(list);
            addAllHashEntries(list);
            this.iter = list.iterator();
        }

        public boolean hasNext() {
            return iter.hasNext();
        }

        public Map.Entry<K, V> next() {
            return last = iter.next();
        }

        public void remove() {
            if (last == null) {
                throw new IllegalStateException("Must call next() before remove().");
            } else {
                iter.remove();
                AbstractHashMap.this.remove(last.getKey());
                last = null;
            }
        }
    }

    private final class MapEntryNull extends AbstractMapEntry<K, V> {

        public K getKey() {
            return null;
        }

        public V getValue() {
            return nullSlot;
        }

        public V setValue(V object) {
            return putNullSlot(object);
        }
    }

    // Instantiated from JSNI
    @SuppressWarnings("unused")
    private final class MapEntryString extends AbstractMapEntry<K, V> {

        private final String key;

        public MapEntryString(String key) {
            this.key = key;
        }

        @SuppressWarnings("unchecked")
        public K getKey() {
            return (K) key;
        }

        public V getValue() {
            return getStringValue(key);
        }

        public V setValue(V object) {
            return putStringValue(key, object);
        }
    }

    /**
     * A map of integral hashCodes onto entries.
     */
    // Used from JSNI.
    @SuppressWarnings("unused")
    private transient JavaScriptObject hashCodeMap;

    /**
     * This is the slot that holds the value associated with the "null" key.
     */
    private transient V nullSlot;

    private transient boolean nullSlotLive;

    private int size;

    /**
     * A map of Strings onto values.
     */
    // Used from JSNI.
    @SuppressWarnings("unused")
    private transient JavaScriptObject stringMap;

    {
        clearImpl();
    }

    public AbstractHashMap() {
    }

    public AbstractHashMap(int ignored) {
        // This implementation of HashMap has no need of initial capacities.
        this(ignored, 0);
    }

    public AbstractHashMap(int ignored, float alsoIgnored) {
        // This implementation of HashMap has no need of load factors or capacities.
        if (ignored < 0 || alsoIgnored < 0) {
            throw new IllegalArgumentException(
                    "initial capacity was negative or load factor was non-positive");
        }
    }

    public AbstractHashMap(Map<? extends K, ? extends V> toBeCopied) {
        this.putAll(toBeCopied);
    }

    @Override
    public void clear() {
        clearImpl();
    }

    public abstract Object clone();

    @Override
    public boolean containsKey(Object key) {
        return (key == null) ? nullSlotLive : (!(key instanceof String)
                ? hasHashValue(key, getHashCode(key)) : hasStringValue((String) key));
    }

    @Override
    public boolean containsValue(Object value) {
        if (nullSlotLive && equals(nullSlot, value)) {
            return true;
        } else if (containsStringValue(value)) {
            return true;
        } else if (containsHashValue(value)) {
            return true;
        }
        return false;
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        return new EntrySet();
    }

    @Override
    public V get(Object key) {
        return (key == null) ? nullSlot : (!(key instanceof String) ? getHashValue(
                key, getHashCode(key)) : getStringValue((String) key));
    }

    @Override
    public V put(K key, V value) {
        return (key == null) ? putNullSlot(value) : (!(key instanceof String)
                ? putHashValue(key, value, getHashCode(key)) : putStringValue(
                (String) key, value));
    }

    @Override
    public V remove(Object key) {
        return (key == null) ? removeNullSlot() : (!(key instanceof String)
                ? removeHashValue(key, getHashCode(key))
                : removeStringValue((String) key));
    }

    @Override
    public int size() {
        return size;
    }

    /**
     * Subclasses must override to return a whether or not two keys or values are
     * equal.
     */
    protected abstract boolean equals(Object value1, Object value2);

    /**
     * Subclasses must override to return a hash code for a given key. The key is
     * guaranteed to be non-null and not a String.
     */
    protected abstract int getHashCode(Object key);

    private native void addAllHashEntries(Collection<?> dest) /*-{
        var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap;
        for (var hashCode in hashCodeMap) {
            // sanity check that it's really an integer
            var hashCodeInt = parseInt(hashCode, 10);
            if (hashCode == hashCodeInt) {
                var array = hashCodeMap[hashCodeInt];
                if (array) {
                  for (var i = 0, c = array.length; i < c; ++i) {
                    dest.@java.util.Collection::add(Ljava/lang/Object;)(array[i]);
                  }
                }
            }
        }
    }-*/;

    private native void addAllStringEntries(Collection<?> dest) /*-{
        var stringMap = this.@java.util.AbstractHashMap::stringMap;
        for (var key in stringMap) {
            // only keys that start with a colon ':' count
            if (key.charCodeAt(0) == 58) {
                var entry = @java.util.AbstractHashMap$MapEntryString::new(Ljava/util/AbstractHashMap;Ljava/lang/String;)(this, key.substring(1));
                dest.@java.util.Collection::add(Ljava/lang/Object;)(entry);
            }
        }
    }-*/;

    private void clearImpl() {
        hashCodeMap = JavaScriptObject.createArray();
        stringMap = JavaScriptObject.createObject();
        nullSlotLive = false;
        nullSlot = null;
        size = 0;
    }

    /**
     * Returns true if hashCodeMap contains any Map.Entry whose value is Object
     * equal to <code>value</code>.
     */
    private native boolean containsHashValue(Object value) /*-{
        var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap;
        for (var hashCode in hashCodeMap) {
            // sanity check that it's really one of ours
            var hashCodeInt = parseInt(hashCode, 10);
            if (hashCode == hashCodeInt) {
                var array = hashCodeMap[hashCodeInt];
                if (array) {
                for (var i = 0, c = array.length; i < c; ++i) {
                    var entry = array[i];
                    var entryValue = entry.@java.util.Map$Entry::getValue()();
                    if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
                        return true;
                    }
                 }
                }
            }
        }
        return false;
    }-*/;

    /**
     * Returns true if stringMap contains any key whose value is Object equal to
     * <code>value</code>.
     */
    private native boolean containsStringValue(Object value) /*-{
        var stringMap = this.@java.util.AbstractHashMap::stringMap;
        for (var key in stringMap) {
            // only keys that start with a colon ':' count
            if (key.charCodeAt(0) == 58) {
                var entryValue = stringMap[key];
                if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
                    return true;
                }
            }
        }
        return false;
    }-*/;

    /**
     * Bridge method from JSNI that keeps us from having to make polymorphic calls
     * in JSNI. By putting the polymorphism in Java code, the compiler can do a
     * better job of optimizing in most cases.
     */
    @SuppressWarnings("unused")
    private boolean equalsBridge(Object value1, Object value2) {
        return equals(value1, value2);
    }

    /**
     * Returns the Map.Entry whose key is Object equal to <code>key</code>,
     * provided that <code>key</code>'s hash code is <code>hashCode</code>;
     * or <code>null</code> if no such Map.Entry exists at the specified
     * hashCode.
     */
    private native V getHashValue(Object key, int hashCode) /*-{
        var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
        if (array) {
            for (var i = 0, c = array.length; i < c; ++i) {
                var entry = array[i];
                var entryKey = entry.@java.util.Map$Entry::getKey()();
                if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
                    return entry.@java.util.Map$Entry::getValue()();
                }
            }
        }
        return null;
    }-*/;

    /**
     * Returns the value for the given key in the stringMap. Returns
     * <code>null</code> if the specified key does not exist.
     */
    private native V getStringValue(String key) /*-{
        return this.@java.util.AbstractHashMap::stringMap[':' + key];
    }-*/;

    /**
     * Returns true if the a key exists in the hashCodeMap that is Object equal to
     * <code>key</code>, provided that <code>key</code>'s hash code is
     * <code>hashCode</code>.
     */
    private native boolean hasHashValue(Object key, int hashCode) /*-{
        var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
        if (array) {
            for (var i = 0, c = array.length; i < c; ++i) {
                var entry = array[i];
                var entryKey = entry.@java.util.Map$Entry::getKey()();
                if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
                    return true;
                }
            }
        }
        return false;
    }-*/;

    /**
     * Returns true if the given key exists in the stringMap.
     */
    private native boolean hasStringValue(String key) /*-{
        return (':' + key) in this.@java.util.AbstractHashMap::stringMap;
    }-*/;

    /**
     * Sets the specified key to the specified value in the hashCodeMap. Returns
     * the value previously at that key. Returns <code>null</code> if the
     * specified key did not exist.
     */
    private native V putHashValue(K key, V value, int hashCode) /*-{
        var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
        if (array) {
            for (var i = 0, c = array.length; i < c; ++i) {
                var entry = array[i];
                var entryKey = entry.@java.util.Map$Entry::getKey()();
                if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
                    // Found an exact match, just update the existing entry
                    var previous = entry.@java.util.Map$Entry::getValue()();
                    entry.@java.util.Map$Entry::setValue(Ljava/lang/Object;)(value);
                    return previous;
                }
            }
        } else {
            array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode] = [];
        }
        var entry = @java.util.MapEntryImpl::new(Ljava/lang/Object;Ljava/lang/Object;)(key, value);
        array.push(entry);
        ++this.@java.util.AbstractHashMap::size;
        return null;
    }-*/;

    private V putNullSlot(V value) {
        V result = nullSlot;
        nullSlot = value;
        if (!nullSlotLive) {
            nullSlotLive = true;
            ++size;
        }
        return result;
    }

    /**
     * Sets the specified key to the specified value in the stringMap. Returns the
     * value previously at that key. Returns <code>null</code> if the specified
     * key did not exist.
     */
    private native V putStringValue(String key, V value) /*-{
        var result, stringMap = this.@java.util.AbstractHashMap::stringMap;
        key = ':' + key;
        if (key in stringMap) {
            result = stringMap[key];
        } else {
            ++this.@java.util.AbstractHashMap::size;
        }
        stringMap[key] = value;
        return result;
    }-*/;

    /**
     * Removes the pair whose key is Object equal to <code>key</code> from
     * <code>hashCodeMap</code>, provided that <code>key</code>'s hash code
     * is <code>hashCode</code>. Returns the value that was associated with the
     * removed key, or null if no such key existed.
     */
    private native V removeHashValue(Object key, int hashCode) /*-{
        var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
        if (array) {
            for (var i = 0, c = array.length; i < c; ++i) {
                var entry = array[i];
                var entryKey = entry.@java.util.Map$Entry::getKey()();
                if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
                    if (array.length == 1) {
                        // remove the whole array
                        delete this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
                    } else {
                        // splice out the entry we're removing
                        array.splice(i, 1);
                    }
                    --this.@java.util.AbstractHashMap::size;
                    return entry.@java.util.Map$Entry::getValue()();
                }
            }
        }
        return null;
    }-*/;

    private V removeNullSlot() {
        V result = nullSlot;
        nullSlot = null;
        if (nullSlotLive) {
            nullSlotLive = false;
            --size;
        }
        return result;
    }

    /**
     * Removes the specified key from the stringMap and returns the value that was
     * previously there. Returns <code>null</code> if the specified key does not
     * exist.
     */
    private native V removeStringValue(String key) /*-{
        var result, stringMap = this.@java.util.AbstractHashMap::stringMap;
        key = ':' + key;
        if (key in stringMap) {
            result = stringMap[key];
            --this.@java.util.AbstractHashMap::size;
            delete stringMap[key];
        }
        return result;
    }-*/;
}
